package com.tgy.algorithm.base._递归;

/**
 * * 规定1和A对应、2和B对应、3和C对应... 26 Z
 *  * 111
 *  * 那么一个数字字符串比如"111”就可以转化为"AAA"、"KA"和"AK
 *  * 给定一个只有数字字符组成的字符串str，返回有多少种转化结果
 */
public class _字符串转换 {

    public static int getAll(String content) {

        int count = doGetAll(content.toCharArray(), 0);
        return count;
    }

    public static int doGetAll(char[] content,int level) {

//        content[level]

        if (level >= content.length) {
            return 1;
        }

        if (content[level] == '0') {
            return 0;
        }

        // 选取一次
        int oneCount = doGetAll(content, level + 1);

        if(level + 1 >= content.length) {
            return oneCount;
        }

        if (content[level] == '1') {
            // 19
           oneCount += doGetAll(content, level + 2);
        }else if (content[level] == '2') {

            // 0 - 6
            if (content[level + 1] >= '0' && content[level + 1] <= '6') {
                oneCount += doGetAll(content, level + 2);
            }
        }

        return oneCount;
    }

    public static int getAll2(char[] content) {

        int len = content.length;
        int[] cache = new int[len+1];
        cache[len] = 1;

        for (int i = len - 1; i >= 0; i--) {

            if (content[i] == '0')  {
                cache[i] = 0;
                continue;
            }

            int oneCount = cache[i+1];
            if (i+1 < len) {
                if (content[i] == '1') {
                    oneCount += cache[i+2];
                }else if (content[i] == '2') {
                    if (content[i + 1] >= '0' && content[i + 1] <= '6') {
                        oneCount += cache[i+2];
                    }
                }
            }

            cache[i] = oneCount;
        }

        return cache[0];
    }

    public static void main(String[] args) {
//        int all = getAll("226");
        int all = getAll2("111".toCharArray());
        // 134217728
        System.out.println(all);
    }
}
